La programmation générique est un concept incroyablement puissant qui permet de créer des algorithmes quelconques faisant totalement abstraction du type d'objets qu'ils manipuleront. On les utilise généralement dans les collections, de façon à créer des collections génériques pouvant contenir ultimement n'importe quoi. Bien que les collections soient l'exemple le plus commun, on peut si on le désire implémenter n'importe quelle classe ou fonction de façon générique.
Le concept de programmation générique ne date pas d'hier. Il a été implémenté pour la première fois en 1983, dans le langage Ada 83 (la première version de ce langage simple et versatile, qui devint orienté objet en 1995). C'est toutefois avec les templates de C++ que la programmation générique a été plus connue et répandue chez les programmeurs. Java supporte la programmation générique depuis la version 1.5 et C# et VB.NET depuis la version 2.
On peut voir la programmation générique comme un paramétrage du type: en plus de passer des paramètres à une méthode, on y passe également le type d'objets ou de valeurs qu'elle devra manipuler. La méthode ou la classe elle-même est codée de façon à pouvoir fonctionner pour n'importe quoi. Le type devient alors un paramètre comme un autre, à la différence qu'il n'est pas énuméré avec les autres paramètres mais placé entre des <chevrons> après le nom de la classe. On utilisera typiquement la lettre T pour représenté un type générique (mais c'est une simple question de convention, toute lettre ou nom pourrait être utilisé pour cet usage).
Par exemple, supposons que l'on décide d'implémenter une classe Pile qui nous permettrait d'empiler des objets les uns sur les autres selon la structure bien connue. On pourrait créer une Pile faite pour y empiler un type d'objet précis, selon notre application. Il est toutefois beaucoup plus efficace de créer une Pile générique, pouvant gérer n'importe quel type d'objet d'une instanciation à l'autre.
On fera alors:
class PileGénérique<T>
{
// On implémente la pile ici
}
Notez le <T> placé immédiatement après le nom de la classe. C'est ce T qui rend notre Pile générique. Lorsqu'on instanciera une PileGénérique, on définira le type d'objets ou de valeurs à y être empilées. Plusieurs PileGénériques pourront co-exister, chacune contenant des objets de types différents.
La collection est une application très fréquente de la programmation générique parce qu'ici l'abstraction du type assouplit considérablement la classe sans apporter aucun coût supplémentaire. En effet, le type des objets qui seront placés dans la pile n'affecte en rien le comportement de la pile elle-même, qui n'a à la limite pas besoin de savoir ce qu'elle empile pour faire son travail correctement.
Lorsque l'on décidera d'instancier une PileGénérique, on fera:
PileGénérique<int> pi = new PileGénérique<int>();
On déclare ici pi, une PileGénérique d'entiers, puis on l'instancie comme étant une nouvelle PileGénérique d'entiers (sans passer de paramètres au constructeur). La seule différence entre cette déclaration et une autre qui ne serait pas générique est la présence du <int> après le nom de la classe.
pi est donc une instance de PileGénérique qui est faite pour empiler des nombres entiers. On ne pourra pas y empiler autre chose et en fait au niveau du compilateur c'est exactement comme si on avait créé le code pour traiter des entiers depuis le début. Aucun casting n'est impliqué nulle part dans son utilisation, ce qui rend le tout très efficace.
Si on décide d'utiliser une pile de chaînes de caractères, on n'a qu'à faire:
PileGénérique<string> pi = new PileGénérique<string>();
Même chose pour y empiler des instances d'Assiettes, une classe qu'on aura créée nous-mêmes:
PileGénérique<Assiette> pi = new PileGénérique<Assiette>();
Voyons voir comment pourrait être implémentée cette pile. Évidemment il y a plusieurs possibilités mais nous en choisirons une arbitrairement simplement pour démontrer la généricité de la chose.
Supposons qu'on décide de stocker nos éléments dans un tableau. On conserve le nombre d'éléments de notre tableau dans une variable à part et on peut ainsi aisément implémenter les trois fonctionnalités courantes d'une pile: Push (empiler), Pop (dépiler) et Peek (regarder ce qu'on dépilerait, mais en le laissant sur la pile).
Disons qu'on décide de commencer par un tableau de 10 cases, qu'on augmentera ensuite au fur et à mesure de l'exécution lorsque nécessaire. Si c'était un tableau d'entiers, on le déclarerait simplement ainsi:
private int[] data = new int[10];
Ici toutefois on veut que le tableau puisse contenir n'importe quoi, selon le type de la pile. On fera donc un tableau de T:
private T[] data = new T[10];
C'est tout simple, T représente le type de notre pile, on utilise T partout où on veut référer à ce type, que ce soit dans le type des attributs, le type d'un paramètre à une méthode ou le type de retour d'une méthode.
On gardera le nombre d'items dans une variable entière. On a donc jusqu'à maintenant:
class PileGénérique<T>
{
private T[] data = new T[10];
private int nbItems = 0;
// On implémente la pile ici
}
Commençons par la méthode Push. Une opération Push, dans une pile, prend un item et le met sur la pile, par-dessus tous les autres déjà présents. Ici, question d'être générique, l'item qu'on recevra en paramètre sera de type T. La méthode ne retourne rien.
public void Push(T item)
{
if (nbItems < 10)
{
data[nbItems++] = item;
}
else
{
Array.Resize(ref data, data.GetLength(0)+1);
data[nbItems++] = item;
}
}
Ainsi, lorsque notre nombre d'items dans la pile est plus petit que 10, on ne fait que placer l'item à la prochaine case dans la pile (n'oublions pas que le tableau commence à 0, alors le nombre d'items contient du coup le numéro de la case où placer le prochain. Il pourra être incrémenté après ce placement).
Si on a dépassé 10 items, on doit agrandir notre tableau d'une case. On peut utiliser pour ça la méthode statique Resize de Array, en lui passant notre tableau (par référence) et la nouvelle taille (la longueur de la dimension 0 de notre tableau (la première et la seule, c'est un tableau à une dimension...) plus 1. On y stocke ensuite le nouvel item.
Notez que la redimension de tableaux en .NET est fort inefficace puisqu'un tableau est toujours statique. Lorsque l'on redimensionne, en fait on crée un nouveau tableau de la taille voulue et on copie un à un tous les éléments du premier tableau dans le deuxième avant de retourner la référence au nouveau tableau. Il y a des façons plus efficaces d'implémenter une pile de ce genre et si la dimension de notre collection est appelée à changer constamment cette méthode n'est pas la meilleure. On y reviendra, pour l'instant tout ce qu'on veut c'est rapidement montrer la généricité de la pile.
La méthode Pop est tout aussi simple: on retourne le dernier élément de la Pile. Dépendamment de notre application, on pourrait décider de réduire le tableau après coup, question de libérer de la mémoire. Question de garder tout ça très simple, supposons qu'on ne se préoccupe pas de ça. Notre fonction Pop pourrait ressembler à ceci:
public T Pop()
{
if (nbItems == 0)
return default(T);
else
return data[--nbItems];
}
Notez le type de retour de la fonction!
Notez aussi qu'on décrémente nbItems avant de retourner la case du tableau, puisque les tableaux sont indexés à partir de 0.
Notez également le cas d'exception: que retourne-t-on quand on n'a aucun item dans notre tableau? On aurait pu retourner la case 0 (vide) sans problème (il aurait fallu simplement ne pas toucher à nbItems), mais on a choisi d'être explicite.
On aurait pu penser à retourner null, ce qui serait bien logique au fond. Toutefois c'est impossible et notre programme ne compilera pas si on tente de le faire. La raison? Null ne peut pas être converti en T à tous les coups puisque T pourrait être un type valeur comme int ou double qui ne peuvent pas contenir null puisque ce ne sont pas des références.
On utilisera alors dans ce cas default(T), qui sera converti en l'objet T par défaut. Dans le cas de n'importe quel type référence, ça équivaut à null. Dans le cas d'un type par valeur, ça équivaut à la valeur par défaut (0 pour les nombres, False pour les booléens...).
La méthode Peek est encore plus simple, puisqu'elle retourne la même chose que Pop mais n'enlève rien de la pile:
public T Peek()
{
if (nbItems == 0)
return default(T);
else
return data[nbItems-1];
}
Voyons maintenant comment il nous sera simple d'empiler n'importe quoi dans notre super Pile. Créons une classe Assiette, définie par une couleur et une épaisseur:
public class Assiette
{
public string couleur;
public double épaisseur;
public Assiette(string couleur, double épaisseur)
{
this.couleur = couleur;
this.épaisseur = épaisseur;
}
}
On peut maintenant empiler des Assiettes comme il se doit. Mais notre pile peut nous permettre également d'empiler n'importe quoi d'autre, comme par exemple des nombres entiers:
static void Main(string[] args)
{
Console.WriteLine("Je crée une pile d'assiettes");
PileGénérique<Assiette> p = new PileGénérique<Assiette>();
Assiette a;
Console.WriteLine();
Console.WriteLine("Je prends une assiette");
a = p.Pop();
if (a != null)
Console.WriteLine(a.couleur);
else
Console.WriteLine("null");
Console.WriteLine();
Console.WriteLine("J'empile deux assiettes");
p.Push(new Assiette("rouge",1));
p.Push(new Assiette("bleue",2));
Console.WriteLine();
Console.WriteLine("Je prends une assiette");
a = p.Pop();
Console.WriteLine(a.couleur);
Console.WriteLine("Je regarde la prochaine assiette");
a = p.Peek();
Console.WriteLine(a.couleur);
Console.WriteLine("Je prends une assiette");
a = p.Pop();
Console.WriteLine(a.couleur);
Console.WriteLine("Je regarde la prochaine assiette");
a = p.Peek();
if (a != null)
Console.WriteLine(a.couleur);
else
Console.WriteLine("null");
Console.WriteLine();
Console.WriteLine("Je crée une pile d'entiers");
PileGénérique<int> pi = new PileGénérique<int>();
Console.WriteLine("Je prends un entier");
Console.WriteLine(pi.Pop());
Console.WriteLine();
Console.WriteLine("J'empile deux entiers");
pi.Push(5);
pi.Push(10);
Console.WriteLine("Je prends deux entiers et je les additionne");
Console.WriteLine(pi.Pop() + pi.Pop());
Console.ReadLine();
}
Un itérateur est une fonctionnalité fort intéressante qui nous permet de prendre en charge l'instruction foreach dans une classe. En effet, il est possible de faire, avec un tableau par exemple, quelque chose comme:
int[] tab = new int[10];
foreach (int i in tab)
{
Console.WriteLine(i);
}
L'instruction foreach parcourt simplement le tableau d'un bout à l'autre, sans qu'on ait besoin de lui donner les dimension du tableau - tout cela est implicite au tableau lui-même.
Concrètement, l'instruction foreach cache la complexité de l'interface IEnumerator de l'espace de noms System.Collections. Il est en effet possible d'utiliser la méthode GetEnumerator() d'un tableau pour obtenir un IEnumerator contenant les membres MoveNext, Reset et Current qu'on peut utiliser pour parcourir le tableau. Par exemple, ceci est valide:
IEnumerator ie = tab.GetEnumerator();
for (int i = 0; i < tab.GetLength(0); i++)
{
ie.MoveNext();
Console.WriteLine(ie.Current);
}
En fait, lorsqu'on utilise le foreach, c'est exactement ce qui se passe mais de façon cachée.
Sachant cela, il est possible de créer des classes implémentant l'interface IEnumerator à leur façon, définissant MoveNext, Reset et Current comme on le désire. Toutefois c'est un peu compliqué inutilement.
C'est là qu'interviennent les itérateurs. Ils nous permettent de prendre en charge le foreach sans devoir implémenter au complet IEnumerator. Concrètement:
La façon la plus simple de créer un itérateur est d'implémenter la méthode GetEnumerator(). Elle peut fonctionner comme on veut, tant qu'elle utilise yield return successivement pour retourner plusieurs éléments du même type. Par exemple, ceci:
using System.Collections;
public class test
{
public IEnumerator GetEnumerator()
{
yield return "les";
yield return "itérateurs";
yield return "c'est";
yield return "cool";
}
}
class Program
{
static void Main(string[] args)
{
foreach (string i in new test())
{
Console.Write(i + " ");
}
}
}
Produira la sortie:
Les itérateurs c'est cool
Notre itérateur peut faire partie de n'importe quelle classe et retourner n'importe quoi (tant qu'il s'agira de données du même type) de n'importe quelle façon. Tant qu'il s'appelle GetEnumerator(), a un type de retour IEnumerator et utilise yield return, toutes les méthodes de IEnumerable seront implémentées automatiquement pour nous et notre classe supportera le foreach.
On peut également définir plusieurs itérateurs différents dans une classe et à ce moment-là en utiliser un en particulier dans notre foreach. Lorsqu'on ne précise aucun itérateur au foreach, il utilise GetEnumerator().
Un itérateur nommé doit être de type IEnumerable. Il peut avoir n'importe quel nom et même accepter des paramètres. Il doit utiliser yield return pour retourner plusieurs valeurs du même type.
Pour l'utiliser avec le foreach, on devra explicitement passer un itérateur à "in" plutôt qu'une simple instance d'un objet. Par exemple:
using System.Collections;
public class test
{
public IEnumerator GetEnumerator()
{
yield return "les";
yield return "itérateurs";
yield return "c'est";
yield return "cool";
}
public IEnumerable itérateurNumérique(int début, int fin)
{
for (int i = début; i <= fin; i++)
yield return i;
}
}
class Program
{
static void Main(string[] args)
{
foreach (int i in new test().itérateurNumérique(10,20))
{
Console.Write(i + " ");
}
}
}
Produira la sortie:
10 11 12 13 14 15 16 17 18 19 20
Remarquez que nos deux itérateurs habitent côte à côte dans la classe test sans aucun problème.
Un itérateur générique fonctionne exactement de la même façon qu'un itérateur standard. Une simple petite différence:
Notez que si on veut, on peut créer un itérateur dans la section get d'une propriété plutôt que dans une fonction. GetEnumerator() est une fonction, mais lorsque l'on crée un énumérateur nommé, le choix est à nous.
Par exemple, on pourrait ajouter à notre PileGénérique un itérateur qui énumère les éléments de notre pile de haut en bas, puis un autre (nommé, dans une propriété) qui les énumérerait dans l'ordre inverse.
public IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < nbItems; i++)
yield return data[i];
}
public IEnumerable<T> énumérateurInverse
{
get
{
for (int i = nbItems-1; i >= 0; i--)
yield return data[i];
}
}
On pourrait donc ajouter à notre Main de tout à l'heure quelque chose qui nous permettrait d'énumérer les assiettes dans notre pile:
Console.WriteLine("J'énumère le contenu de ma pile");
foreach (Assiette aa in p)
Console.WriteLine("Une assiette {0} de {1} cm d'épaisseur", aa.couleur, aa.épaisseur);
Console.WriteLine();
Console.WriteLine("J'énumère le contenu de ma pile à l'envers");
foreach (Assiette aa in p.énumérateurInverse)
Console.WriteLine("Une assiette {0} de {1} cm d'épaisseur", aa.couleur, aa.épaisseur);
Console.WriteLine();
Si on veut être conforme aux normes des collections génériques énumérables, il est recommandé d'implémenter complètement l'interface IEnumerable<T>. Pour ce faire, il suffit de:
Le fait d'implémenter IEnumerable<T> garantit que l'on respecte le contrat de l'itération générique et que nos itérateurs seront définis conformément aux normes. Tout programmeur qui utilise notre classe pourra être confiant qu'un foreach fonctionnera normalement, et qu'il sera capable d'obtenir notre itérateur afin de le gérer "à la main", sans foreach, s'il le désire.
Notre pile devient donc (les parties modifiées sont en gras):
using System.Collections;
using System.Collections.Generic;
class PileGénérique<T> :IEnumerable<T>
{
private T[] data = new T[1];
private int nbItems = 0;
public void Push(T item)
{
if (nbItems < 1)
{
data[nbItems++] = item;
}
else
{
Array.Resize(ref data, data.GetLength(0)+1);
data[nbItems++] = item;
}
}
public T Pop()
{
if (nbItems == 0)
return default(T);
else
return data[--nbItems];
}
public T Peek()
{
if (nbItems == 0)
return default(T);
else
return data[nbItems-1];
}
public IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < nbItems; i++)
yield return data[i];
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public IEnumerable<T> énumérateurInverse
{
get
{
for (int i = nbItems - 1; i >= 0; i--)
yield return data[i];
}
}
}
Le Main final qui nous permet de jouer avec des piles est donc:
static void Main(string[] args)
{
Console.WriteLine("Je crée une pile d'assiettes");
PileGénérique<Assiette> p = new PileGénérique<Assiette>();
Assiette a;
Console.WriteLine();
Console.WriteLine("Je prends une assiette");
a = p.Pop();
if (a != null)
Console.WriteLine(a.couleur);
else
Console.WriteLine("null");
Console.WriteLine();
Console.WriteLine("J'empile deux assiettes");
p.Push(new Assiette("rouge",1));
p.Push(new Assiette("bleue",2));
Console.WriteLine();
Console.WriteLine("J'énumère le contenu de ma pile");
foreach (Assiette aa in p)
Console.WriteLine("Une assiette {0} de {1} cm d'épaisseur", aa.couleur, aa.épaisseur);
Console.WriteLine();
Console.WriteLine("J'énumère le contenu de ma pile à l'envers");
foreach (Assiette aa in p.énumérateurInverse)
Console.WriteLine("Une assiette {0} de {1} cm d'épaisseur", aa.couleur, aa.épaisseur);
Console.WriteLine();
Console.WriteLine("Je prends une assiette");
a = p.Pop();
Console.WriteLine(a.couleur);
Console.WriteLine("Je regarde la prochaine assiette");
a = p.Peek();
Console.WriteLine(a.couleur);
Console.WriteLine("Je prends une assiette");
a = p.Pop();
Console.WriteLine(a.couleur);
Console.WriteLine("Je regarde la prochaine assiette");
a = p.Peek();
if (a != null)
Console.WriteLine(a.couleur);
else
Console.WriteLine("null");
Console.WriteLine();
Console.WriteLine("Je crée une pile d'entiers");
PileGénérique<int> pi = new PileGénérique<int>();
Console.WriteLine("Je prends un entier");
Console.WriteLine(pi.Pop());
Console.WriteLine();
Console.WriteLine("J'empile deux entiers");
pi.Push(5);
pi.Push(10);
Console.WriteLine("Je prends deux entiers et je les additionne");
Console.WriteLine(pi.Pop() + pi.Pop());
Console.ReadLine();
}
Ce qui génère la sortie suivante:
Je crée une pile d'assiettes
Je prends une assiette
null
J'empile deux assiettes
J'énumère le contenu de ma pile
Une assiette rouge de 1 cm d'épaisseur
Une assiette bleue de 2 cm d'épaisseur
J'énumère le contenu de ma pile à l'envers
Une assiette bleue de 2 cm d'épaisseur
Une assiette rouge de 1 cm d'épaisseur
Je prends une assiette
bleue
Je regarde la prochaine assiette
rouge
Je prends une assiette
rouge
Je regarde la prochaine assiette
null
Je crée une pile d'entiers
Je prends un entier
0
J'empile deux entiers
Je prends deux entiers et je les additionne
15